# 合并两个有序链表
# 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

# 示例：

# 输入：1->2->4, 1->3->4
# 输出：1->1->2->3->4->4

# Definition for singly-linked list.


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(0)
        tmp = head
        while l1 and l2:
            if l1.val < l2.val:
                tmp.next = l1
                tmp = tmp.next
                l1 = l1.next
            else:
                tmp.next = l2
                tmp = tmp.next
                l2 = l2.next

        if l1:
            tmp.next = l1
        if l2:
            tmp.next = l2

        return head.next


def test_mergeTwoLists():
    a = ListNode(1)
    b = ListNode(2)
    c = ListNode(4)
    a.next = b
    b.next = c

    d = ListNode(1)
    e = ListNode(3)
    f = ListNode(4)
    d.next = e
    e.next = f
    node = Solution().mergeTwoLists(a, d)
    from list_node import get_value
    assert get_value(node) == [1, 1, 2, 3, 4, 4]


def test_mergeTwoLists2():
    a = ListNode(1)
    b = ListNode(2)
    c = ListNode(4)
    a.next = b
    b.next = c

    d = ListNode(1)
    e = ListNode(3)
    f = ListNode(4)
    g = ListNode(5)
    d.next = e
    e.next = f
    f.next = g
    node = Solution().mergeTwoLists(a, d)
    from list_node import get_value
    assert get_value(node) == [1, 1, 2, 3, 4, 4, 5]

if __name__ == "__main__":
    a = ListNode(1)
    b = ListNode(2)
    c = ListNode(4)
    a.next = b
    b.next = c

    d = ListNode(1)
    e = ListNode(3)
    f = ListNode(4)
    d.next = e
    e.next = f
    node = Solution().mergeTwoLists(a, d)
    from list_node import get_value
    print(get_value(node))
